1. Field of the Invention
The present invention relates to a system and method for evaluating the cosine of relatively small angles, i.e. angles whose magnitude are close to zero.
2. Description of the Related Art
In an article entitled xe2x80x9cThe CORDIC Trigonometric Computing Techniquexe2x80x9d, authored by Jack E. Volder, and published in IRE Trans. Electron. Comput. EC-8:330-334 (1959), Volder describes the Coordinate Rotation Digital Computer (CORDIC). In this article, which is incorporated by reference in its entirety, Volder discloses a computational algorithm based on a convergent series of elementary rotations. This algorithm will be referred to herein as the CORDIC algorithm. The CORDIC algorithm in its various realizations may be used to compute a variety of elementary functions such as, e.g., sine, cosine, tangent, arctangent, exponential, logarithm, hyperbolic sine, hyperbolic cosine, hyperbolic tangent, etc. In addition, the CORDIC algorithm may also be used to compute two-dimensional rotations, multiplications, divisions and square roots.
The CORDIC algorithm receives an input point (X0,Y0) and an input angle xcex0, and applies a series of iterations to these input operands. Each iteration of the series operates on a current intermediate point (Xi,Yi) and a current residual angle xcexi, and generates an updated intermediate point (Xi+1,Yi+1) and an updated residual angle xcexi+1. In the first iteration, the current intermediate point is taken to be the input point (X0,Y0) and the current residual angle is taken to be the input angle xcex0. A mathematical analysis of the CORDIC algorithm reveals that the intermediate point (Xi,Yi) converges as the iteration index increases. The limiting resultant point is given by the equations                               X          R                =                              K            ⁢                          xe2x80x83                        ⁢                          R              0                        ⁢                          cos              ⁡                              (                                                      θ                    0                                    +                                      λ                    0                                                  )                                              =                                    lim                              i                →                ∞                                      ⁢                          X              i                                                          (        1        )                                                      Y            R                    =                                    K              ⁢                              xe2x80x83                            ⁢                              R                0                            ⁢                              sin                ⁡                                  (                                                            θ                      0                                        +                                          λ                      0                                                        )                                                      =                                          lim                                  i                  →                  ∞                                            ⁢                              Y                i                                                    ,                            (        2        )            
where K is a known constant, R0 is the radius of the point (X0,Y0) with respect to the origin, and xcex80 is the counter-clockwise angle of the input point (X0,Y0) with respect to the positive x axis. Geometrically, the resultant point (XR,YR) is a rotated and scaled image of the input point (X0,Y0). In other words, the resultant point (XRYR) is that point which arises from rotating the input point (X0,Y0) by input angle xcex0 and then radially extending the interim rotated point by factor K. One advantage of the CORDIC algorithm lies in the fact that it implements this scaled rotation more efficiently than a direct computation of equations (1) and (2) which would generally require a pair of hardware multiplies and trigonometric evaluations.
Suppose that the input point (X0,Y0) is chosen to be (1/K,0). In this case, the initial radius R0 equals 1/K and the angle xcex80 of the input point with respect to the positive x axis equals zero. According to equations (1) and (2), after N iterations of the CORDIC algorithm, the x-coordinate XN approximates the value cos(xcex0), and the y-coordinate YN approximates the value sin(xcex0). By various arrangements of the initial conditions and the structure of the CORDIC algorithm, a great variety of elementary functions may be evaluated.
The CORDIC algorithm operates on the input point (X0,Y0) and the input angle xcex0 by applying an iterative series of pseudo-rotations governed by the following system of equations:
Yi+1=Yi+"xgr"i2xe2x88x92iXixe2x80x83xe2x80x83(3)
Xi+1=Xixe2x88x92"xgr"i2xe2x88x92iYixe2x80x83xe2x80x83(4)
xcexi+1=xcexixe2x88x92"xgr"ixc2x7xcex1i,xe2x80x83xe2x80x83(5)
xcex1i=arctan(2xe2x88x92i),xe2x80x83xe2x80x83(6)
where the iteration index i is greater than or equal to zero, and where the scalar factor "xgr"i takes the value xc2x11 depending on the sign of the residual angle xcexi. In particular, if the residual angle xcexi is positive, the factor "xgr"i takes the value +1, and thus, equations (6) and (7) implement a pseudo-rotation of the intermediate point (Xi,Yi) by the angle xcex1i, and equation (8) computes an updated residual angle 80 i+1 by subtracting the angle xcex1i from the current residual xcexi. Conversely, if the residual angle xcexi is negative, the factor "xgr"i takes the value xe2x88x921, and thus, equations (6) and (7) implement a pseudo-rotation of the intermediate point (Xi,Yi) by the angle xe2x88x92xcex1i, and equation (8) computes the updated residual by adding the angle xcex1i to the current residual.
It is noted that equations (6) and (7) implement a pseudo-rotation of the point (Xi,Yi) by the rotation angle xcex1i. The direction of the pseudo-rotation (clockwise or counter-clockwise) depends on the value of factor "xgr"i. The resultant point (Xi+1,Yi+1) may be equivalently expressed by the relations
Yi+1={square root over (1+2xe2x88x922i+L )}Ri sin(xcex8i+"xgr"ixcex1i),xe2x80x83xe2x80x83(7)
Xi+1={square root over (1+2xe2x88x922i+L )}Ri cos(xcex8i+"xgr"ixcex1i),xe2x80x83xe2x80x83(8)
where Ri is the radius of the point (Xi,Yi), and xcex8i is the angle of the point (Xi,Yi) with respect to the positive x axis, i.e.
Yi=Ri sin(xcex8i),xe2x80x83xe2x80x83(9)
Xi=Ri cos(xcex8i).xe2x80x83xe2x80x83(10)
The resultant point (Xi+1,Yi+1) is slightly farther from the origin than the source point (Xi,Yi), i.e. by a factor of {square root over (1+2xe2x88x922i+L )}, and for this reason the resultant point cannot be said to be a pure rotation of the source point.
As the iteration index i increases, the intermediate point (Xi,Yi) converges to the limiting resultant point given by equations (1) and (2). Furthermore, the residual angle xcexi converges to zero. It can be shown that the CORDIC algorithm exhibits an exponential rate of convergence, i.e. after N iterations of the CORDIC algorithm the residual angle xcexN has an absolute value smaller than 2xe2x88x92(Nxe2x88x921). In addition, the coordinates of the intermediate point (XN,YN) approximate the corresponding coordinates of the limiting resultant (XRYR) to within a tolerance of KR02xe2x88x92(Nxe2x88x921). In other words, each iteration of the CORDIC algorithm yields an additional bit of precision in the binary representations of XN and YN.
Iteration equations (6), (7) and (8) may be efficiently implemented with (a) shifters configured to perform the indicated multiplications by powers of two, (b) adders configured to perform the addition and subtraction operations, and (c) a comparator to test the residual value for controlling the conditional additions and subtractions. In particular, it is noted that the iteration equations (6), (7) and (8) may be evaluated without performing hardware multiplies or trigonometric evaluations. The angular constants a, may be stored in a lookup table. These features allow the CORDIC algorithm to compute approximations to XR and YR in significantly less time than direct implementations of equations (1) and (2) which achieve a comparable precision.
It is noted that multiplication of a binary number by xc2xd corresponds to shifting the bits of the binary number to the right one position with respect the binary point. In general, multiplication of a binary number by the factor 2xe2x88x92L corresponds to shifting the bits of the binary number to the right L bit positions.
Various ways to improve the CORDIC algorithm have been sought. One prior art method for improving the CORDIC algorithm has been advanced by Timmermann et al. in a paper entitled xe2x80x9cModified CORDIC Algorithm with Reduced Iterationsxe2x80x9d, Electronic Letters, vol. 25, no.15, pages 950-951, copyright 1989, which is hereby incorporated by reference in its entirety. Timmermann et al. make the observation that the first iterations of the CORDIC algorithm make the most significant contributions since the rotation angles xcex1i decrease with increasing iteration index i. The last iterations each contribute one additional bit of precision to the resultant values. Thus, an initial number J of CORDIC iterations may be performed, and the remaining number (N+1xe2x88x92J) of CORDIC iterations which would normally be required to achieve N bits of precision may be replaced by a single rotation step. If the number J is appropriately chosen the residual angle xcexJ will be sufficiently close to zero so that
|cos(xcexJ)xe2x88x921| less than 2xe2x88x92N.xe2x80x83xe2x80x83(11)
In particular, it can be shown that inequality (11) will be satisfied if   J   greater than                     N        +        1            2        .  
For example, integer J may be set equal to the smallest integer greater than or equal to             N      +      1        2    .
The intermediate point (XJ,YJ) resulting from the Jth CORDIC iteration may be rotated through the residual angle xcexJ using the relations
YT=xcexJXJ+YJ,xe2x80x83xe2x80x83(12)
XT=XJxe2x88x92xcexJYJ,xe2x80x83xe2x80x83(13)
where the sine and cosine of xcexJ are replaced by xcexJ and 1 respectively. The output point (XT,YT) approximates the point given by (KJR0 cos(xcex80+xcex0),KJR0 sin(xcex80+xcex0)) with N bits of precision, where
KJ={square root over (1+2xe2x88x922(0)+L )}{square root over (1+2xe2x88x922(1)+L )} . . . {square root over (1+2xe2x88x922(Jxe2x88x921)+L )}.xe2x80x83xe2x80x83(14)
If the rotation step given by equations (12) and (13) are implemented with a latency smaller than the latency of (N+1xe2x88x92J) CORDIC stages, the rotation step may advantageously replace computation of the last (N+1xe2x88x92J) CORDIC stages of the standard CORDIC algorithm. This procedure of performing J CORDIC iterations, where       J     greater than                   N        +        1            2        ,
followed by the rotation step of equations (12) and (13) will be referred to herein as the Timmermann algorithm.
The Timmermann algorithm uses small angle approximations for sine and cosine which induce error in the resultant point (XT,YT). To control this error, the Timmermann algorithm is forced to use a large number of CORDIC stages       (                  i        .        e        .                  xe2x80x83                ⁢        J             greater than                         N          +          1                2              )    .
The sine and cosine are replaced with their small angle approximations because evaluation of these functions even for small angles according to prior art techniques generally requires an inordinately large time delay. Thus, there exists a need for a fast and accurate mechanism for evaluating the cosine and/or sine functions on small angles.
The CORDIC algorithm and the Timmermann algorithm have gained a wide field of application due to their computational efficiency. Thus, any improvements to the CORDIC algorithm, especially improvements which exceed the speed and performance of the Timmermann algorithm, are highly desirable.
The cosine function finds use in many and various fields of engineering and scientific endeavor. For example; in the Timmermann algorithm described above, the cosine function is replaced by its small angle approximation, i.e. cos(xcex8)≈1. This approximation and others are quite typically used in an effort to avoid the computational burden of evaluating a Taylor series for cosine, or the time delay of accessing a lookup table. Thus, any technique or mechanism for increasing the speed of a cosine function evaluation is profoundly desirable, and would result in significant improvements in algorithms which rely heavily on cosine computations.
A cosine computation unit according to the present invention comprises a logical processing unit and an addition unit. The logical processing unit comprises an input bus with a plurality of input lines for receiving an input angle value. The logical processing unit includes a first plurality of gates, preferably AND gates, coupled to the input bus. Each gate of the first plurality of gates couples to two or more of the input lines. The logical processing unit generates N output operands on N corresponding output buses. At least one of the output buses includes (a) at least one output line coupled to an output of one of the first plurality of gates, and (b) at least one output line coupled to one of the input lines of the input bus. The number N of output buses is greater than or equal to two.
The addition unit couples to the N output buses of the logical processing unit, and is configured to perform an addition of the N binary operands provided on the N output buses. The addition unit generates a resultant number which represents the cosine of the input operand conveyed on the input bus.
In one embodiment of the logical processing unit, each of the output buses comprises (a) one or more output lines which are driven by corresponding gates of the first plurality of gates and (b) one or more additional output lines each of which is set equal to a logical zero value.
The cosine computation unit operates under the assumption that a leading number of the most significant bits of the input operands are equal to zero. Such a situation arises in the CORDIC algorithms. After a succession of CORDIC stages/iterations, the residual angle from the last CORDIC stage is guaranteed to have a leading number of zeros which depends on the number of CORDIC stages in the succession.